package leetcode.动态规划.零一背包;

public class Leetcode416 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum+nums[i];
        }
        if(sum%2==1){
            return false;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for(int j = target;j>0;j--){
                if(j-i>=0){
                    dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
                }
            }
        }
        return dp[target]==target;
    }
}
